#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#define PARENT(i) (i-1)/2
#define LEFT(i) 2*(i)+1
#define RIGHT(i) 2*(i)+2
#define SWAP(a,b) \
    do { int tmp = a; a = b; b = tmp; } \
    while(0)

void print(int a[], int len);

void Min_Heapify(int a[], int len, int i)
{
    int left = LEFT(i);
    int right = RIGHT(i);
    int small;

    if (left < len && a[left] < a[i]) 
        small = left;
    else 
        small = i;
    if (right < len && a[right] < a[small]) 
        small = right;
    
    if (small != i) {
        SWAP(a[i], a[small]);
        Min_Heapify(a, len, small);
    }
}

void Build_Heap(int a[], int len)
{
    for (int i = PARENT(len-1); i >= 0; i--) {
        Min_Heapify(a, len, i);
    }

    /*print(a, len);*/
}

int Extract_Min(int a[], int len)
{
    int re = a[0];
    SWAP(a[0], a[len-1]);
    Min_Heapify(a, len-1, 0);

    return re;
}

void Enqueue(int a[], int *plen, int ele)
{
    int len = *plen;
    a[len++] = ele;
    *plen = len;

    for (int i = PARENT(len-1); i >= 0; i--) {
        Min_Heapify(a, len, i);
    }
}

int Min_Heap(int a[])
{
    return a[0];
}

void Heap_Sort(int a[], int len)
{
    Build_Heap(a, len);
    for (int i = len - 1; i >= 0; i--) {
        SWAP(a[i], a[0]);
        len--;
        Min_Heapify(a, len, 0);
    }
    
}

void print(int a[], int len)
{
    for (int i = 0; i < len; i++) {
        printf("%d  ", a[i]);
    }
    printf("\n");
}

int main(int argc, char *argv[])
{
    int heap[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};   
    int len = sizeof(heap)/sizeof(heap[0]);
    Build_Heap(heap, len);
    Enqueue(heap, &len, 20);
    /*printf("%d\n", Extract_Min(heap, len));*/
    Heap_Sort(heap, len);
    print(heap, len);

    return 0;
}

